<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>
    <script>
        class ArrayList {
            list = []

            insert(val) {
                this.list.push(val)
            }

            toString() {
                return this.list.join(' ')
            }

            // 冒泡排序
            bubbleSort() {
                let list = [...this.list]
                for (let i = 0; i < list.length; i++) {
                    for (let j = 0; j < list.length - i - 1; j++) {
                        if (list[j] > list[j + 1]) {
                            let temp = list[j]
                            list[j] = list[j + 1]
                            list[j + 1] = temp
                        }
                    }
                }
                this.list = list
            }

            swap(m, n) {
                let temp = m
                m = n
                n = temp
            }

            // 选择排序
            selectSort() {
                let list = [...this.list]
                
                for (let i = 0; i < list.length; i++) {
                    let min = i
                    for (let j = min + i; j < list.length; j++) {
                        if (list[min] > list[j]) {
                            min = j
                        }
                    }
                    let temp = list[i]
                    list[i] = list[min]
                    list[min] = temp
                }
                this.list = list
            }


            // 插入排序
            inertSort() {
                let list = [...this.list]
                for(let i=1; i<list.length; i++) {
                    let temp = list[i]
                    let j=i
                    while(list[j-1] > temp && j>0) {
                        list[j] = list[j-1]
                        j--
                    }
                    list[j]=temp
                }
                this.list=list
            }

            // 希尔排序
            shellSort() {
                let list = [...this.list]
                let gap = Math.floor(list.length / 2) 
                while(gap >= 1) {
                    for(let i=gap; i<list.length; i++) {
                        let temp = list[i]
                        let j = i
                        while(list[j-gap] > temp && j > gap - 1) {
                            list[j] = list[j - gap]
                            j -= gap
                        }
                        list[j] = temp
                    }

                    gap = Math.floor(gap / 2)
                } 
                this.list = list
            }

        }
        

        let a = new ArrayList()
        a.insert(10)
        a.insert(9)
        a.insert(8)
        a.insert(7)
        a.insert(6)
        a.insert(5)
        a.insert(4)
        a.insert(3)
        a.insert(2)
        a.insert(1)
        // a.bubbleSort()
        // a.selectSort()
        // a.inertSort()
        a.shellSort()

        console.log(a.toString())
    </script>
</body>

</html>